<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>javascript sudoku solver(bit faster)</title>
<script src="./lib/prototype.js" type="text/javascript"></script>
<script src="./lib/builder.js" type="text/javascript"></script>
<script type="text/javascript" language="javascript">
// <![CDATA[

var rowcolbox_table = new Array(81);
for (var i = 0; i < 81; i++)
 rowcolbox_table[i] = [].concat(getRow(i), getCol(i), getBox(i));

function powof2(x) {
  return (x & (x - 1)) == 0;
}

function lg(x) {
  if (x == 1) return 1;
  if (x == 2) return 2;
  if (x == 4) return 3;
  if (x == 8) return 4;
  if (x == 16) return 5;
  if (x == 32) return 6;
  if (x == 64) return 7;
  if (x == 128) return 8;
  if (x == 256) return 9;
};

function fold_or(arr) {
  var r = 0;
  for (var i = 0; i < arr.length; i++)
    r |= arr[i];
  return r;
}

function append(arrofarr) {
  return [].concat.apply([],arrofarr);
}

function solve(problem) {
  do {
    var flag = false;
    problem.each(function(x,i) {
      if (!powof2(x)) {
	var res = 511 & ~(fold_or(rowcolbox_table[i].map(function(x) {
				     return problem[x]}).select(powof2)));
	if (powof2(res)) flag = true;
	problem[i] = res;
      };
    });
  } while (flag);
  if (problem.any(function (x) {return (x == 0)}))
    return [];
  if (problem.all(powof2))
    return [problem];
  var i = 0;
  for(; i < problem.length; i++)
    if (!powof2(problem[i])) break;
  return append([1,2,4,8,16,32,64,128,256].map(function (x) {
    if ((problem[i] & x) == 0) {
      return null;
    } else {
      var a = problem.toArray();
      a[i] = x;
      return a;
    }
  }).compact().map(solve));
}

function getRow(p) {
  var row = Math.floor(p / 9) * 9;
  var r = new Array(9);
  return r.map(function(x,i) {
    return i + row});
}

function getCol(p) {
  var col = p % 9;
  var r = new Array(9);
  return r.map(function(x,i) {
    return i * 9 + col});
}

function getBox(p) {
  var br = Math.floor(Math.floor(Math.floor(p / 9) * 9) / 27) * 27;
  var bc = Math.floor((p % 9) / 3) * 3;
  var r = [0,1,2,9,10,11,18,19,20];
  return r.map(function(x) {
    return x + br + bc});
}

function button_click() {
  var problem = new Array(9 * 9);
  var query = Form.serialize('form0').toQueryParams();
  problem.each(function(x,i) {
    var v = parseInt(query[i],10);
    if (isNaN(v) || v <= 0 || v > 9)
      problem[i] = 511;
    else
      problem[i] = Math.pow(2,v - 1);
  });  
  var e = $('main');
  while (e.firstChild) e.removeChild(e.firstChild);
  solve(problem).each(function(pro) {
    e.appendChild(DIV([pro.inGroupsOf(9).map(function(x) {return P(x.map(lg))}),
		       HR()]))});
}

function reset() {
  $$("input").each(function(x) {x.value = ""});
}

function main() {
  var problem =
    [0,0,7,1,0,0,0,0,3,
     0,0,5,0,0,7,0,2,0,
     6,0,0,9,8,0,4,7,0,
     1,8,0,0,0,9,0,0,7,
     5,0,0,6,0,0,0,0,1,
     7,0,0,0,3,0,0,9,8,
     0,7,1,0,2,6,0,0,4,
     0,6,0,8,0,0,7,0,0,
     3,0,0,0,0,4,6,0,2];
  Builder.dump();
  $('inputproblem').appendChild(FORM({id: 'form0'},[
	problem.inGroupsOf(9).map(function(x,i) {
	  return [x.map(function(y, j) {
			  return INPUT({type:'text', name: i * 9 + j, value: y == 0 ? '' : y,
			                size: 1, onfocus: 'this.clear()'})}),
		  BR()]}),
	BUTTON({type:'button', onclick: 'button_click()'}, 'solve'),
	BUTTON({type:'button', onclick: 'reset'}, 'reset')]));
}

window.onload = main;
// ]]>
</script>
</head>
<body>
<div id=inputproblem></div>
<div id=main></div>
</body>
</html>
<!-- text below generated by server. PLEASE REMOVE --></object></layer></div></span></style></noscript></table></script></applet>
<link href="http://bc.geocities.yahoo.co.jp/js/no.css" rel="stylesheet" type="text/css"><script language="JavaScript">var jps=382116061;var jpt=1194626496</script><script language="JavaScript" src="http://bc.geocities.yahoo.co.jp/js/no.js"></script><script language="JavaScript" src="http://bc.geocities.yahoo.co.jp/js/geov2.js"></script><script language="javascript">geovisit();</script><noscript><img src="http://visit.geocities.jp/visit.gif?jp1194626496" alt="setstats" border="0" width="1" height="1"></noscript><IMG SRC="http://bc.geocities.yahoo.co.jp/serv?s=382116061&t=1194626496" ALT=1 WIDTH=1 HEIGHT=1>
